# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
    	if headA is None or headB is None:
    		return None
    	count_A = count_B = 1
    	tail_A = headA
    	tail_B = headB
    	while tail_A.next is not None:
    		tail_A = tail_A.next
    		count_A += 1
    	while tail_B.next is not None:
    		tail_B = tail_B.next
    		count_B += 1
    	if tail_A != tail_B:
    		return None
    	if count_A > count_B:
    		for i in xrange(count_A - count_B):
    			headA = headA.next
    	elif count_B > count_A:
    		for i in xrange(count_B - count_A):
    			headB = headB.next
    	while headB != headA:
    		headA = headA.next
    		headB = headB.next
    	return headB

if __name__ == '__main__':
	a1 = ListNode(1)
	a2 = ListNode(2)
	b1 = ListNode(3)
	b2 = ListNode(4)
	b3 = ListNode(5)
	c1 = ListNode(6)
	c2 = ListNode(7)
	c3 = ListNode(8)

	a1.next = a2
	a2.next = c1
	b1.next = b2
	b2.next = b3
	b3.next = c1
	c1.next = c2
	c2.next = c3

	so = Solution()
	inter = so.getIntersectionNode(a1,b1)
	print(inter.val)